import collections
import heapq
from typing import List


class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        min_idx, min_val = (-1, -1), float("inf")
        graph = collections.defaultdict(dict)
        for edge in connections:
            if edge[1] not in graph[edge[0]] or edge[2] < graph[edge[0]][edge[1]]:
                graph[edge[0]][edge[1]] = edge[2]
                graph[edge[1]][edge[0]] = edge[2]
                if edge[2] < min_val:
                    min_idx, min_val = (edge[0], edge[1]), edge[2]

        ans = 0

        waiting = {i for i in range(1, n + 1)}
        heap = []

        # 添加最短的边
        ans += min_val
        waiting.remove(min_idx[0])
        waiting.remove(min_idx[1])

        for n2, v2 in graph[min_idx[0]].items():
            if n2 in waiting:
                heapq.heappush(heap, (v2, n2))
        for n2, v2 in graph[min_idx[1]].items():
            if n2 in waiting:
                heapq.heappush(heap, (v2, n2))

        while heap and waiting:
            v1, n1 = heapq.heappop(heap)
            if n1 in waiting:
                ans += v1
                waiting.remove(n1)
                for n2, v2 in graph[n1].items():
                    if n2 in waiting:
                        heapq.heappush(heap, (v2, n2))

        return ans if not waiting else -1


if __name__ == "__main__":
    print(Solution().minimumCost(n=3, connections=[[1, 2, 5], [1, 3, 6], [2, 3, 1]]))  # 6
    print(Solution().minimumCost(n=4, connections=[[1, 2, 3], [3, 4, 4]]))  # -1
